package 单周赛;

import java.util.*;

/**
 * @
 * @date 2024/12/01
 */
public class 第426场单周赛 {

    public static void main(String[] args) {

        第426场单周赛 impl = new 第426场单周赛();
        System.out.println(Arrays.toString(impl.maxTargetNodes(
                new int[][]{{0, 1}, {0, 2}, {2, 3}, {2, 4}},
                new int[][]{{0, 1}, {0, 2}, {0, 3}, {2, 7}, {1, 4}, {4, 5}, {4, 6}},
                2

        )));

        System.out.println(impl.getLargestOutlier(new int[]{6, -31, 50, -35, 41, 37, -42, 13}));

    }

    private Map<Integer, List<Integer>> gird1 = new HashMap<>();
    private Map<Integer, List<Integer>> gird2 = new HashMap<>();

    /**
     * bfs找到edges2中每个节点的 <= k-1 层的所有节点数，用最大的那个节点和 edges1 节点拼接
     */
    public int[] maxTargetNodes(int[][] edges1, int[][] edges2, int k) {

        for (int[] edge : edges1) {
            List<Integer> list1 = gird1.get(edge[0]);
            if (list1 == null) {
                list1 = new ArrayList<>();
                gird1.put(edge[0], list1);
            }
            list1.add(edge[1]);
            List<Integer> list0 = gird1.get(edge[1]);
            if (list0 == null) {
                list0 = new ArrayList<>();
                gird1.put(edge[1], list0);
            }
            list0.add(edge[0]);
        }
        for (int[] edge : edges2) {
            List<Integer> list1 = gird2.get(edge[0]);
            if (list1 == null) {
                list1 = new ArrayList<>();
                gird2.put(edge[0], list1);
            }
            list1.add(edge[1]);
            List<Integer> list0 = gird2.get(edge[1]);
            if (list0 == null) {
                list0 = new ArrayList<>();
                gird2.put(edge[1], list0);
            }
            list0.add(edge[0]);
        }

        int[] maxTargetArr1 = new int[edges1.length + 1];
        int[] maxTargetArr2 = new int[edges2.length + 1];


        int max2 = 0;
        for (int i = 0; i < maxTargetArr2.length; i++) {
            max2 = Math.max(max2, getMaxSum(i, gird2, k - 1));
        }

        for (int i = 0; i < maxTargetArr1.length; i++) {
            maxTargetArr1[i] = getMaxSum(i, gird1, k) + max2;
        }
        return maxTargetArr1;
    }

    private int getMaxSum(int i, Map<Integer, List<Integer>> gird, int k) {
        if (k < 0) {
            return 0;
        }

        int sum = 1;
        Set<Integer> visit = new HashSet<>();
        Deque<Integer> queue = new ArrayDeque<>();
        queue.addLast(i);
        visit.add(i);

        while (!queue.isEmpty() && k-- > 0) {
            int size = queue.size();
            while (size-- > 0) {
                Integer cur = queue.pollFirst();

                List<Integer> list = gird.get(cur);
                if (list != null) {
                    for (Integer nextNum : list) {
                        if (visit.add(nextNum)) {
                            queue.addLast(nextNum);
                        }
                    }
                }
            }
            sum += queue.size();
        }

        return sum;
    }

    public int smallestNumber(int n) {

        int curSum = 0;
        int cnt = 0;
        while (curSum < n) {
            curSum += Math.pow(2, cnt);
            cnt++;

        }
        return curSum;
    }

    /**
     * 哈希表
     * 假设特殊数字的和是 x , 异常值是 y , 数组总和为 sum
     * 那么 2*x+y == sum
     * x 是数组的某个元素，枚举 x ，先用哈希表存储 y 出现的次数
     * 注意：当 x == y 时 ，y的出现次数需要 >= 2！！！
     */
    public int getLargestOutlier(int[] nums) {
        int sum = 0;
        Map<Integer, Integer> map = new HashMap<>();
        for (int num : nums) {
            sum += num;
            map.put(num, map.getOrDefault(num, 0) + 1);
        }

        int ans = Integer.MIN_VALUE;
        for (int x : nums) {
            int y = sum - 2 * x;
            if (x == y && map.get(x) >= 2) {
                ans = Math.max(ans, y);
            } else if (x != y && map.containsKey(y)) {
                ans = Math.max(ans, y);
            }
        }

        return ans;
    }

    /**
     * 前缀和枚举（超时）
     */
    public int getLargestOutlier2(int[] nums) {
        int[] prefixSum = new int[nums.length + 1];
        for (int i = 0; i < nums.length; i++) {
            prefixSum[i + 1] = prefixSum[i] + nums[i];
        }

        int max = Integer.MIN_VALUE;
        for (int i = 0; i < nums.length; i++) {
            for (int j = 0; j < nums.length; j++) {
                if (i == j) {
                    continue;
                }
                if (prefixSum[i] + (prefixSum[j] - prefixSum[i + 1]) +
                        (prefixSum[nums.length] - prefixSum[j + 1]) == nums[j]) {
                    max = Math.max(max, nums[i]);
                }
            }
        }

        return max;
    }


}
